/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.math.BigInteger;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/22
 */
//大整数
//一个k(1<=k<=80)位的十进制正整数N,就是所谓的大整数.
//请你设计程序,对于给出的某一个大整数N,找到满足p^3+p^2+3p<=n的p的最大值.
public class P9_4_1375 {

    // 计算逼近值，使用二分法
    public static String test(String input) {
        Long longVal;
        try {
            longVal = Long.valueOf(input);
        } catch (Exception ex) {
            longVal = null;
        }
        if (longVal != null) {
            double start = Math.pow(longVal / 2, 1.0 / 3);
            for (long i = (long) start; i < Long.MAX_VALUE; i++) {
                long value = (long) (Math.pow(i, 3) + Math.pow(i, 2) + 3 * i);
                if (value > longVal) {
                    return "" + (i - 1);
                }
            }
        } else {
            BigInteger bi = new BigInteger(input);
            int zeroNum = (input.length() - 2) / 3;
            StringBuilder sb = new StringBuilder().append(1);
            for (int i = 0; i < zeroNum; i++) {
                sb.append(0);
            }
            BigInteger left = new BigInteger(sb.toString());
            BigInteger lastLeft = new BigInteger(sb.toString());
            BigInteger right = new BigInteger(sb.append(0).append(0).toString());
            while (true) {
                BigInteger value = left.pow(3).add(left.pow(2)).add(left.multiply(new BigInteger("" + 3)));
                if (value.compareTo(bi) == 1) {
                    right = new BigInteger(left.toString());
                    left = lastLeft;
                } else if (value.compareTo(bi) == 0) {
                    return value.toString();
                } else {
                    lastLeft = new BigInteger(left.toString());
                    BigInteger range = right.subtract(left).divide(new BigInteger("" + 2));
                    if (range.compareTo(new BigInteger("" + 0)) == 0) {
                        return left.toString();
                    }
                    left = left.add(range);
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        System.out.println(test("1000000000000001000000000000003000000000000001"));
    }
}
